﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CSLearn
{
    internal class DP
    {
        /// <summary>
        /// leetcode  518  零钱兑换2(动态规划/完全背包/组合)
        /// </summary>
        /// <param name="amount"></param>
        /// <param name="coins"></param>
        /// <returns></returns>
        public int Change(int amount, int[] coins)
        {
            int[] dp = new int[amount + 1];
            dp[0] = 1;
            for (int i = 0; i < coins.Length; i++)
            {
                for (int j = coins[i]; j <= amount; j++)
                {
                    dp[j] += dp[j - coins[i]];
                }
            }
            return dp[amount];
        }

        /// <summary>
        /// leetcode  322  零钱兑换(dp/完全背包)
        /// </summary>
        /// <param name="coins"></param>
        /// <param name="amount"></param>
        /// <returns></returns>
        public int CoinChange(int[] coins, int amount)
        {
            int max = amount + 1;
            int[] dp = new int[max];
            Array.Fill(dp, max);
            dp[0] = 0;
            for (int i = 0; i < coins.Length; i++)
            {
                for (int j = coins[i]; j <= amount; j++)
                {
                    dp[j] = Math.Min(dp[j - coins[i]] + 1, dp[j]);
                }
            }
            return dp[amount] > amount ? -1 : dp[amount];
        }

        /// <summary>
        /// leetcode  2684  矩阵中移动的最大次数
        /// </summary>
        /// <param name="grid"></param>
        /// <returns></returns>
        public int MaxMoves(int[][] grid)
        {
            int m = grid.Length;
            int n = grid[0].Length;
            int[][] dp = new int[m][];
            for (int i = 0; i < m; i++)
            {
                dp[i] = new int[n];
            }
            for (int j = n - 1; j > 0; j--)
            {
                for (int i = 0; i < m; i++)
                {
                    if (i > 0 && grid[i - 1][j - 1] < grid[i][j])
                        dp[i - 1][j - 1] = Math.Max(dp[i - 1][j - 1], dp[i][j] + 1);
                    if (grid[i][j - 1] < grid[i][j])
                        dp[i][j - 1] = Math.Max(dp[i][j - 1], dp[i][j] + 1);
                    if (i < m - 1 && grid[i + 1][j - 1] < grid[i][j])
                        dp[i + 1][j - 1] = Math.Max(dp[i + 1][j - 1], dp[i][j] + 1);
                }
            }
            int res = 0;
            for (int i = 0; i < m; i++)
            {
                res = dp[i][0] > res ? dp[i][0] : res;
            }
            return res;
        }

        /// <summary>
        /// leetcode  2312  卖木头块(DP+记忆化搜索)
        /// </summary>
        /// <param name="m"></param>
        /// <param name="n"></param>
        /// <param name="prices"></param>
        /// <returns></returns>
        public long SellingWood(int m, int n, int[][] prices)
        {
            long[][] dp = new long[m + 1][];
            int[][] pr = new int[m + 1][];
            for (int i = 0; i <= m; i++)
            {
                dp[i] = new long[n + 1];
                pr[i] = new int[n + 1];
                for (int j = 0; j <= n; j++)
                {
                    dp[i][j] = -1;
                }
            }
            foreach (int[] price in prices)
            {
                pr[price[0]][price[1]] = price[2];
            }
            DFSSellingWood(m, n, dp, pr);
            return dp[m][n];
        }

        void DFSSellingWood(int m, int n, long[][] dp, int[][] pr)
        {
            if (dp[m][n] != -1) return;
            long p = pr[m][n];
            for (int i = 1; i <= m / 2; i++)
            {
                DFSSellingWood(i, n, dp, pr);
                DFSSellingWood(m - i, n, dp, pr);
                long t = dp[i][n] + dp[m - i][n];
                p = Math.Max(p, t);
            }
            for (int i = 1; i <= n / 2; i++)
            {
                DFSSellingWood(m, i, dp, pr);
                DFSSellingWood(m, n - i, dp, pr);
                long t = dp[m][i] + dp[m][n - i];
                p = Math.Max(p, t);
            }
            dp[m][n] = p;
        }

        /// <summary>
        /// leetcode  2368  受限条件下可到达节点的数目
        /// </summary>
        /// <param name="n"></param>
        /// <param name="edges"></param>
        /// <param name="restricted"></param>
        /// <returns></returns>
        public int ReachableNodes(int n, int[][] edges, int[] restricted)
        {
            int res = 1;
            List<int>[] canMove = new List<int>[n];
            for (int i = 0; i < n; i++)
            {
                canMove[i] = new List<int>();
            }
            foreach (var item in edges)
            {
                canMove[item[0]].Add(item[1]);
                canMove[item[1]].Add(item[0]);
            }
            bool[] isRestricted = new bool[n];
            for (int i = 0; i < restricted.Length; i++)
            {
                isRestricted[restricted[i]] = true;
            }
            Queue<int> queue = new Queue<int>();
            queue.Enqueue(0);
            while (queue.Count > 0)
            {
                int currentNode = queue.Dequeue();
                isRestricted[currentNode] = true;
                foreach (int item in canMove[currentNode])
                {
                    if (!isRestricted[item])
                    {
                        res++;
                        queue.Enqueue(item);
                    }
                }
            }

            return res;
        }

        /// <summary>
        /// leetcode  2369  检查数组是否存在有效划分(dp)
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public bool ValidPartition(int[] nums)
        {
            int n = nums.Length;
            bool[] dp = new bool[n + 1];
            dp[0] = true;
            if (ValidTwo(nums[0], nums[1]))
                dp[2] = true;
            if (n > 2 && ValidThree(nums[0], nums[1], nums[2]))
                dp[3] = true;
            for (int i = 3; i <= n; i++)
            {
                dp[i] = (dp[i - 2] && ValidTwo(nums[i - 2], nums[i - 1]))
                        || (dp[i - 3] && ValidThree(nums[i - 3], nums[i - 2], nums[i - 1]));
            }
            return dp[n];
        }

        bool ValidTwo(int num1, int num2)
        {
            if (num1 == num2) return true;
            return false;
        }

        bool ValidThree(int num1, int num2, int num3)
        {
            if (num1 == num2 && num1 == num3) return true;
            if (num2 - num1 == 1 && num3 - num2 == 1) return true;
            return false;
        }

        /// <summary>
        /// leetcode  516  最长回文子序列(动态规划)
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public int LongestPalindromeSubseq(string s)
        {
            int n = s.Length;
            int[][] dp = new int[n][];
            for (int i = 0; i < n; i++)
            {
                dp[i] = new int[n];
                dp[i][i] = 1;
            }
            for (int i = n - 1; i >= 0; i--)
            {
                for (int j = i + 1; j < n; j++)
                {
                    if (s[i] == s[j])
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    else
                        dp[i][j] = Math.Max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
            return dp[0][n - 1];
        }

        /// <summary>
        /// leetcode  647  回文子串(动态规划)
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public int CountSubstrings(string s)
        {
            int res = 0;
            int n = s.Length;
            bool[][] dp = new bool[n][];
            for (int i = 0; i < n; i++)
            {
                dp[i] = new bool[n];
            }
            for (int i = n - 1; i >= 0; i--)
            {
                for (int j = i; j < n; j++)
                {
                    if (s[i] == s[j])
                    {
                        if (j - i <= 1)
                        {
                            res++;
                            dp[i][j] = true;
                        }
                        else if (dp[i + 1][j - 1])
                        {
                            res++;
                            dp[i][j] = true;
                        }
                    }
                }
            }
            return res;
        }

        /// <summary>
        /// leetcode  72  编辑距离(动态规划)
        /// </summary>
        /// <param name="word1"></param>
        /// <param name="word2"></param>
        /// <returns></returns>
        public int MinDistance2(string word1, string word2)
        {
            int length1 = word1.Length;
            int length2 = word2.Length;
            int[][] dp = new int[length1 + 1][];
            for (int i = 0; i <= length1; i++)
            {
                dp[i] = new int[length2 + 1];
                dp[i][0] = i;
            }
            for (int j = 0; j <= length2; j++)
            {
                dp[0][j] = j;
            }
            for (int i = 1; i <= length1; i++)
            {
                for (int j = 1; j <= length2; j++)
                {
                    if (word1[i - 1] == word2[j - 1])
                        dp[i][j] = dp[i - 1][j - 1];
                    else
                        dp[i][j] = Math.Min(Math.Min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
            return dp[length1][length2];
        }

        /// <summary>
        /// leetcode  583  两个字符串的删除操作(动态规划)
        /// </summary>
        /// <param name="word1"></param>
        /// <param name="word2"></param>
        /// <returns></returns>
        public int MinDistance(string word1, string word2)
        {
            int length1 = word1.Length;
            int length2 = word2.Length;
            int[][] dp = new int[length1 + 1][];
            for (int i = 0; i <= length1; i++)
            {
                dp[i] = new int[length2 + 1];
                dp[i][0] = i;
            }
            for (int i = 0; i <= length2; i++)
            {
                dp[0][i] = i;
            }
            for (int i = 1; i <= length1; i++)
            {
                for (int j = 1; j <= length2; j++)
                {
                    if (word1[i - 1] == word2[j - 1])
                    {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                    else
                    {
                        dp[i][j] = Math.Min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                    }
                }
            }
            return dp[length1][length2];
        }

        /// <summary>
        /// leetcode  115  不同的子序列(动态规划)
        /// </summary>
        /// <param name="s"></param>
        /// <param name="t"></param>
        /// <returns></returns>
        public int NumDistinct(string s, string t)
        {
            if (s.Length < t.Length) return 0;
            int length1 = s.Length;
            int length2 = t.Length;
            int[][] dp = new int[length1 + 1][];
            string res;
            for (int i = 0; i <= length1; i++)
            {
                dp[i] = new int[length2 + 1];
                dp[i][0] = 1;
            }

            for (int i = 1; i <= length1; i++)
            {
                for (int j = 1; j <= length2; j++)
                {
                    if (s[i - 1] == t[j - 1])
                        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                    else
                        dp[i][j] = dp[i - 1][j];

                    res = $"dp[{i}][{j}] = {dp[i][j]}";
                }
            }

            return dp[length1][length2];
        }

        /// <summary>
        /// leetcode  392  判断子序列(双指针 > 动态规划）
        /// </summary>
        /// <param name="s"></param>
        /// <param name="t"></param>
        /// <returns></returns>
        public bool IsSubsequence(string s, string t)
        {
            if (s.Length == 0) return true;
            if (s.Length > t.Length) return false;
            int left = 0, right = 0;
            while (right < t.Length)
            {
                if (s[left] == t[right])
                    left++;
                if (left == s.Length)
                    return true;

                right++;
            }
            return false;
        }

        /// <summary>
        /// leetcode  2652  倍数求和
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public int SumOfMultiples(int n)
        {
            int res = 0;
            for (int i = 1; i <= n; i++)
            {
                if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0)
                    res += i;
            }
            return res;
        }

        /// <summary>
        /// leetcode  1035  不相交的线(动态规划)
        /// </summary>
        /// <param name="nums1"></param>
        /// <param name="nums2"></param>
        /// <returns></returns>
        public int MaxUncrossedLines(int[] nums1, int[] nums2)
        {
            int m = nums1.Length;
            int n = nums2.Length;
            int[][] dp = new int[m + 1][];
            for (int i = 0; i <= m; i++)
            {
                dp[i] = new int[n + 1];
            }
            for (int i = 1; i <= m; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    if (nums1[i - 1] == nums2[j - 1])
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    else
                        dp[i][j] = Math.Max(dp[i - 1][j], dp[i][j - 1]);
                }
            }

            return dp[m][n];
        }

        /// <summary>
        /// leetcode  1143  最长公共子序列(动态规划)
        /// </summary>
        /// <param name="text1"></param>
        /// <param name="text2"></param>
        /// <returns></returns>
        public int LongestCommonSubsequence(string text1, string text2)
        {
            int m = text1.Length;
            int n = text2.Length;
            //int[][] dp = new int[m + 1][];
            //for (int i = 0; i <= m; i++)
            //{
            //    dp[i] = new int[n + 1];
            //}
            //for (int i = 1; i <= m; i++)
            //{
            //    for (int j = 1; j <= n; j++)
            //    {
            //        if (text1[i - 1] == text2[j - 1])
            //            dp[i][j] = dp[i - 1][j - 1] + 1;
            //        else
            //            dp[i][j] = Math.Max(dp[i - 1][j], dp[i][j - 1]);
            //    }
            //}
            //return dp[m][n];
            int[] dp = new int[n + 1];
            for (int i = 1; i <= m; i++)
            {
                int pre = dp[0];
                for (int j = 1; j <= n; j++)
                {
                    int cur = dp[j];
                    if (text1[i - 1] == text2[j - 1])
                    {
                        dp[j] = pre + 1;
                    }
                    else
                    {
                        dp[j] = Math.Max(dp[j], dp[j - 1]);
                    }
                    pre = cur;
                }
            }
            return dp[n];
        }

        /// <summary>
        /// leetcode  718  最长重复子数组(动态规划)
        /// </summary>
        /// <param name="nums1"></param>
        /// <param name="nums2"></param>
        /// <returns></returns>
        public int FindLength(int[] nums1, int[] nums2)
        {
            int m = nums1.Length;
            int n = nums2.Length;
            int[] dp = new int[n + 1];
            int max = 0;

            for (int i = 1; i <= m; i++)
            {
                for (int j = n; j > 0; j--)
                {
                    if (nums1[i - 1] == nums2[j - 1])
                    {
                        dp[j] = dp[j - 1] + 1;
                    }
                    else
                        dp[j] = 0;
                    if (max < dp[j]) max = dp[j];
                }
            }
            return max;
        }

        /// <summary>
        /// leetcode  674  最长连续递增序列(动态规划, 贪心)
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int FindLengthOfLCIS(int[] nums)
        {
            int n = nums.Length;
            if (n <= 1) return n;
            int pre = 1, max = 1;

            for (int i = 1; i < n; i++)
            {
                if (nums[i] > nums[i - 1])
                {
                    pre++;
                    max = Math.Max(max, pre);
                }
                else
                    pre = 1;
            }
            return max;
        }

        /// <summary>
        /// leetcode  300  最长递增子序列(动态规划)
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int LengthOfLIS(int[] nums)
        {
            int n = nums.Length;
            if (n <= 1) return n;
            int[] dp = new int[n];
            for (int i = 0; i < n; i++)
            {
                dp[i] = 1;
            }
            int max = 1;

            for (int i = 1; i < n; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if (nums[i] > nums[j])
                    {
                        dp[i] = Math.Max(dp[i], dp[j] + 1);
                    }
                }
                max = Math.Max(max, dp[i]);
            }
            return max;
        }

        /// <summary>
        /// leetcode  714  买卖股票的最佳时机6含有手续费(动态规划)
        /// </summary>
        /// <param name="prices"></param>
        /// <param name="fee"></param>
        /// <returns></returns>
        public int MaxProfit6(int[] prices, int fee)
        {
            int n = prices.Length;
            if (n <= 1) return 0;
            int[][] dp = new int[2][];
            dp[0] = new int[] { -prices[0] - fee, 0 };
            dp[1] = new int[2];

            for (int i = 1; i < n; i++)
            {
                dp[1][0] = Math.Max(dp[0][0], dp[0][1] - prices[i] - fee);
                dp[1][1] = Math.Max(dp[0][1], dp[0][0] + prices[i]);

                dp[0][0] = dp[1][0];
                dp[0][1] = dp[1][1];
            }

            return dp[1][1];
        }

        /// <summary>
        /// leetcode  309  买卖股票的最佳时机5含冷冻期(动态规划)
        /// </summary>
        /// <param name="prices"></param>
        /// <returns></returns>
        public int MaxProfit5(int[] prices)
        {
            int n = prices.Length;
            if (n <= 1) return 0;
            int[][] dp = new int[2][];
            for (int i = 0; i < 2; i++)
            {
                dp[i] = new int[4];
            }
            dp[0][0] = -prices[0];

            for (int i = 1; i < n; i++)
            {
                dp[1][0] = Math.Max(dp[0][0], Math.Max(dp[0][2], dp[0][3]) - prices[i]);
                dp[1][1] = dp[0][0] + prices[i];
                dp[1][2] = dp[0][1];
                dp[1][3] = Math.Max(dp[0][3], dp[0][2]);

                dp[0][0] = dp[1][0];
                dp[0][1] = dp[1][1];
                dp[0][2] = dp[1][2];
                dp[0][3] = dp[1][3];

                Console.Write($"dp[{i}] : ");
                for (int j = 0; j < 4; j++)
                {
                    Console.Write(dp[1][j] + "  ");
                }
            }

            return Math.Max(Math.Max(dp[1][1], dp[1][2]), dp[1][3]);
        }

        /// <summary>
        /// leetcode  188  买卖股票的最佳时机4(动态规划)
        /// </summary>
        /// <param name="k"></param>
        /// <param name="prices"></param>
        /// <returns></returns>
        public int MaxProfit4(int k, int[] prices)
        {
            int n = prices.Length;
            int m = 2 * k;
            if (n <= 1) return 0;

            int[][] dp = new int[2][];

            for (int i = 0; i < 2; i++)
            {
                dp[i] = new int[m];
            }
            for (int j = 0; j < m; j += 2)
            {
                dp[0][j] = -prices[0];
            }

            for (int i = 1; i < n; i++)
            {
                dp[1][0] = Math.Max(dp[0][0], -prices[i]);
                dp[1][1] = Math.Max(dp[0][1], dp[0][0] + prices[i]);

                dp[0][0] = dp[1][0];
                dp[0][1] = dp[1][1];
                for (int j = 2; j < m; j += 2)
                {
                    dp[1][j] = Math.Max(dp[0][j], dp[0][j - 1] - prices[i]);
                    dp[1][j + 1] = Math.Max(dp[0][j + 1], dp[0][j] + prices[i]);

                    dp[0][j] = dp[1][j];
                    dp[0][j + 1] = dp[1][j + 1];
                }
            }

            return dp[1][m - 1];
        }

        /// <summary>
        /// leetcode  123  买卖股票的最佳时机3(动态规划)
        /// </summary>
        /// <param name="prices"></param>
        /// <returns></returns>
        public int MaxProfit3(int[] prices)
        {
            int n = prices.Length;
            if (n <= 1) return 0;

            int[][] dp = new int[n][];
            for (int i = 0; i < n; i++)
            {
                dp[i] = new int[4];
            }
            dp[0][0] = -prices[0];
            dp[0][2] = -prices[0];

            for (int i = 1; i < n; i++)
            {
                dp[1][0] = Math.Max(dp[0][0], -prices[i]);
                dp[1][1] = Math.Max(dp[0][1], dp[0][0] + prices[i]);
                dp[1][2] = Math.Max(dp[0][2], dp[0][1] - prices[i]);
                dp[1][3] = Math.Max(dp[0][3], dp[0][2] + prices[i]);

                dp[0][0] = dp[1][0];
                dp[0][1] = dp[1][1];
                dp[0][2] = dp[1][2];
                dp[0][3] = dp[1][3];
            }

            return dp[1][3];
        }

        /// <summary>
        /// leetcode  121  买卖股票的最佳时机(动态规划)
        /// </summary>
        /// <param name="prices"></param>
        /// <returns></returns>
        public int MaxProfit(int[] prices)
        {
            int n = prices.Length;
            if (n <= 1) return 0;

            int[][] dp = new int[2][];

            for (int i = 0; i < 2; i++)
            {
                dp[i] = new int[2];
            }
            dp[0][0] = -prices[0];

            for (int i = 1; i < n; i++)
            {
                dp[i % 2][0] = Math.Max(dp[(i - 1) % 2][0], -prices[i % 2]);
                dp[i % 2][1] = Math.Max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i % 2]);
            }

            return dp[(n - 1) % 2][1];
        }

        /// <summary>
        /// leetcode  139  单词拆分(动态规划/完全背包/排列)
        /// </summary>
        /// <param name="s"></param>
        /// <param name="wordDict"></param>
        /// <returns></returns>
        public bool WordBreak(string s, IList<string> wordDict)
        {
            int n = s.Length;
            bool[] dp = new bool[n + 1];
            dp[0] = true;
            for (int i = 1; i <= n; i++)
            {
                //for (int j = 0; j < i; j++)
                //{
                foreach (string word in wordDict)
                {
                    int len = word.Length;
                    if (i >= len && dp[i - len] && word.Equals(s.Substring(i - len, len)))
                    {
                        dp[i] = true;
                        break;
                    }
                }
                //string temp = s.Substring(j, i - j);
                //if (dp[j] && wordDict.Contains(temp))
                //    dp[i] = true;
                //}
            }

            return dp[n];
        }

        /// <summary>
        /// leetcode  279  完全平方数(动态规划/完全背包)
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public int NumSquares(int n)
        {
            if (n == 1) return 1;

            int[] dp = new int[n + 1];
            Array.Fill(dp, n);
            dp[0] = 0;
            for (int i = 1; i * i <= n; i++)
            {
                for (int j = i * i; j <= n; j++)
                {
                    dp[j] = Math.Min(dp[j], dp[j - i * i] + 1);
                }
            }

            return dp[n];
        }

        /// <summary>
        /// leetcode  377  组合总和4(动态规划/完全背包/排列)
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public int CombinationSum4(int[] nums, int target)
        {
            int[] dp = new int[target + 1];
            dp[0] = 1;
            for (int j = 0; j <= target; j++)
            {
                for (int i = 0; i < nums.Length; i++)
                {
                    if (j - nums[i] >= 0)
                        dp[j] += dp[j - nums[i]];
                }
            }

            return dp[target];
        }

        /// <summary>
        /// leetcode  322  零钱兑换(动态规划/完全背包)
        /// </summary>
        /// <param name="coins"></param>
        /// <param name="amount"></param>
        /// <returns></returns>
        public int CoinChangeOld(int[] coins, int amount)
        {
            int max = amount + 1;
            int[] dp = new int[amount + 1];
            Array.Fill(dp, max);
            dp[0] = 0;
            for (int i = 0; i < coins.Length; i++)
            {
                for (int j = coins[i]; j <= amount; j++)
                {
                    dp[j] = Math.Min(dp[j], dp[j - coins[i]] + 1);
                }
            }

            return dp[amount] > amount ? -1 : dp[amount];
        }

        /// <summary>
        /// leetcode  518  零钱兑换2(动态规划/完全背包/组合)
        /// </summary>
        /// <param name="amount"></param>
        /// <param name="coins"></param>
        /// <returns></returns>
        public int ChangeOld(int amount, int[] coins)
        {
            int[] dp = new int[amount + 1];
            dp[0] = 1;

            for (int i = 0; i < coins.Length; i++)
            {
                for (int j = coins[i]; j <= amount; j++)
                {
                    dp[j] += dp[j - coins[i]];
                }
            }

            return dp[amount];
        }

        /// <summary>
        /// leetcode  474  一和零(动态规划/01背包)
        /// </summary>
        /// <param name="strs"></param>
        /// <param name="m"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public int FindMaxForm(string[] strs, int m, int n)
        {
            int[][] dp = new int[m + 1][];
            for (int i = 0; i <= m; i++)
            {
                dp[i] = new int[n + 1];
            }
            foreach (string str in strs)
            {
                int zeroNum = 0;
                int oneNum = 0;
                foreach (char c in str)
                {
                    if (c == '0') zeroNum++;
                    else oneNum++;
                }
                for (int i = m; i >= zeroNum; i--)
                {
                    for (int j = n; j >= oneNum; j--)
                    {
                        dp[i][j] = Math.Max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                    }
                }
            }
            return dp[m][n];
        }

        /// <summary>
        /// leetcode  494  目标和(动态规划/01背包)
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public int FindTargetSumWays(int[] nums, int target)
        {
            int sum = 0;
            foreach (int x in nums)
            {
                sum += x;
            }
            if (sum < Math.Abs(target))
                return 0;
            if ((sum + target) % 2 != 0)
                return 0;
            int size = Math.Abs((sum + target) / 2);
            int[] dp = new int[size + 1];
            dp[0] = 1;
            for (int i = 0; i < nums.Length; i++)
            {
                for (int j = size; j >= nums[i]; j--)
                {
                    dp[j] += dp[j - nums[i]];
                }
            }
            return dp[size];
        }

        /// <summary>
        /// leetcode  1049  最后一块石头的重量2(动态规划/01背包)
        /// </summary>
        /// <param name="stones"></param>
        /// <returns></returns>
        public int LastStoneWeightII(int[] stones)
        {
            int n = stones.Length;
            if (n == 1) return stones[0];

            int sum = 0;
            foreach (int stone in stones)
            {
                sum += stone;
            }
            int target = sum / 2;
            int[] dp = new int[target + 1];
            for (int i = 0; i < n; i++)
            {
                for (int j = target; j >= stones[i]; j--)
                {
                    dp[j] = Math.Max(dp[j], dp[j - stones[i]] + stones[i]);
                }
            }

            return sum - 2 * dp[target];
        }

        /// <summary>
        /// leetcode  416  分割等和子集(动态规划/01背包)
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public bool CanPartition(int[] nums)
        {
            int n = nums.Length;
            if (n == 0) return false;
            int sum = 0;
            foreach (int i in nums)
            {
                sum += i;
            }
            if (sum % 2 != 0) return false;
            sum /= 2;

            int[] dp = new int[sum + 1];
            for (int i = 0; i < n; i++)
            {
                for (int j = sum; j >= nums[i]; j--)
                {
                    dp[j] = Math.Max(dp[j], dp[j - nums[i]] + nums[i]);
                }
                if (dp[sum] == sum) return true;
            }

            return dp[sum] == sum;
        }

        /// <summary>
        /// leetcode  96  不同的二叉搜索树(动态规划)
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public int NumTrees(int n)
        {
            if (n <= 2) return n;
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;

            for (int i = 2; i <= n; i++)
            {
                for (int j = 1; j <= i; j++)
                {
                    dp[i] += dp[j - 1] * dp[i - j];
                }
            }

            return dp[n];
        }

        /// <summary>
        /// leetcode  343  整数拆分(动态规划)
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public int IntegerBreak(int n)
        {
            int[] dp = new int[n + 1];
            dp[1] = 1;
            for (int i = 2; i <= n; i++)
            {
                for (int j = 1; j <= i - j; j++)
                {
                    dp[i] = Math.Max(dp[i], Math.Max(dp[i - j] * j, j * (i - j)));
                }
            }

            return dp[n];
        }

        /// <summary>
        /// leetcode  63  不同路径2(动态规划)
        /// </summary>
        /// <param name="obstacleGrid"></param>
        /// <returns></returns>
        public int UniquePathsWithObstacles(int[][] obstacleGrid)
        {
            int m = obstacleGrid.Length;
            int n = obstacleGrid[0].Length;
            //int[][] dp = new int[m][];
            //for (int i = 0; i < m; i++)
            //{
            //    dp[i] = new int[n];
            //}
            //for (int i = 1; i < m; i++)
            //{
            //    if (obstacleGrid[i][0] != 0)
            //        break;
            //    dp[i][0] = 1;
            //}
            //for (int i = 1; i < n; i++)
            //{
            //    if (obstacleGrid[0][i] != 0)
            //        break;
            //    dp[0][i] = 1;
            //}
            //for (int i = 1; i < m; i++)
            //{
            //    for (int j = 1; j < n; j++)
            //    {
            //        if (obstacleGrid[i][j] != 0)
            //            dp[i][j] = 0;
            //        else
            //            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            //    }
            //}

            //return dp[m - 1][n - 1];

            int[] dp = new int[n];
            for (int i = 0; i < n && obstacleGrid[0][i] == 0; i++)
            {
                dp[i] = 1;
            }
            for (int i = 1; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (obstacleGrid[i][j] != 0)
                        dp[j] = 0;
                    else if (j > 0)
                        dp[j] += dp[j - 1];
                }
            }
            return dp[n - 1];
        }

        /// <summary>
        /// leetcode  62  不同路径(动态规划)
        /// </summary>
        /// <param name="m"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public int UniquePaths(int m, int n)
        {
            int[] dp = new int[n];
            for (int i = 0; i < n; i++)
            {
                dp[i] = 1;
            }
            for (int i = 1; i < m; i++)
            {
                for (int j = 1; j < n; j++)
                {
                    dp[j] += dp[j - 1];
                }
            }
            return dp[n - 1];
        }

        /// <summary>
        /// leetcode  746  使用最小花费爬楼梯
        /// </summary>
        /// <param name="cost"></param>
        /// <returns></returns>
        public int MinCostClimbingStairs(int[] cost)
        {
            int n = cost.Length;
            int pre = 0;
            int cur = 0;
            int next = 0;

            for (int i = 1; i < n; i++)
            {
                next = Math.Min(pre + cost[i - 1], cur + cost[i]);
                pre = cur;
                cur = next;
            }
            return next;
        }

        /// <summary>
        /// leetcode  70  爬楼梯(动态规划)
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public int ClimbStairs(int n)
        {
            if (n <= 2) return n;
            int pre = 1;
            int cur = 2;
            int next = 0;
            for (int i = 2; i < n; i++)
            {
                next = pre + cur;
                pre = cur;
                cur = next;
            }
            return next;
        }

        /// <summary>
        /// leetcode  509  斐波那契数(动态规划)
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public int Fib(int n)
        {
            if (n <= 1) return n;

            int pre = 0;
            int cur = 1;
            int next = 0;
            for (int i = 1; i < n; i++)
            {
                next = pre + cur;

                pre = cur;
                cur = next;
            }

            return next;
        }

        /// <summary>
        /// leetcode  122  买卖股票的最佳时机2(动态规划)
        /// </summary>
        /// <param name="prices"></param>
        /// <returns></returns>
        public int MaxProfit2(int[] prices)
        {
            int n = prices.Length;
            if (n <= 1) return 0;


            int[][] dp = new int[2][];
            dp[0] = new int[] { 0, -prices[0] };
            dp[1] = new int[2];
            for (int i = 1; i < prices.Length; i++)
            {
                dp[1][0] = Math.Max(dp[0][0], dp[0][1] + prices[i]);
                dp[1][1] = Math.Max(dp[0][1], dp[0][0] - prices[i]);

                //dp[0] = dp[1];
                dp[0][0] = dp[1][0];
                dp[0][1] = dp[1][1];
            }
            return dp[1][0];
        }

        /// <summary>
        /// leetcode  213  打家劫舍2(动态规划)
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int Rob2(int[] nums)
        {
            int n = nums.Length;
            if (n == 0) return 0;
            if (n == 1) return nums[0];
            if (n == 2) return Math.Max(nums[0], nums[1]);

            int a = nums[0];
            int b = Math.Max(a, nums[1]);
            int res1 = Math.Max(a, b);
            for (int i = 2; i < n - 1; i++)
            {
                res1 = Math.Max(b, a + nums[i]);
                a = b;
                b = res1;
            }
            a = nums[1];
            b = Math.Max(a, nums[2]);
            int res2 = Math.Max(a, b);
            for (int i = 1; i < n; i++)
            {
                res2 = Math.Max(b, a + nums[i]);
                a = b;
                b = res2;
            }

            return Math.Max(res1, res2);
        }


        /// <summary>
        /// leetcode  198  打家劫舍
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int Rob(int[] nums)
        {
            int n = nums.Length;
            if (n == 0) return 0;
            if (n == 1) return nums[0];
            if (n == 2) return Math.Max(nums[0], nums[1]);

            int[] dp = new int[2];
            dp[0] = nums[0];
            dp[1] = Math.Max(nums[0], nums[1]);
            int res = 0;

            for (int i = 2; i < n; i++)
            {
                res = Math.Max(dp[1], dp[0] + nums[i]);

                dp[0] = dp[1];
                dp[1] = res;
            }

            return res;

            //return 0;
        }

    }
}
